#include<bits/stdc++.h>
using namespace std;

typedef struct node {
    char data;
    struct node* left;
    struct node* right;
}treenode;

void createtree(treenode* root, string s) {//建立二叉树
    root->data = s[0];
    int toward = 0;
    stack<treenode*>arr;//用队列存放元素
    arr.push(root);
    for (int i = 1; i < s.size(); i++) {
        if (s[i] == '(') {
            toward = 1;
        }
        else if (s[i] == ')') {
            arr.pop();
        }
        else if (s[i] == ',') {
            toward = 2;
            if (arr.size() != 1 && s[i - 1] != '(') {
                arr.pop();
            }
        }
        else {
            treenode* newnode = new treenode;
            newnode->left = newnode->right = NULL;
            if (toward == 1) {//左孩子
                arr.top()->left = newnode;
                newnode->data = s[i];
                arr.push(newnode);
            }
            else {//右孩子
                arr.top()->right = newnode;
                newnode->data = s[i];
                arr.push(newnode);
            }
        }
    }
}

void preSearch(treenode* node, char arr[],int index,char maxpath[],int &maxlen) {//前序遍历
    arr[index] = node->data;
    if (!node->left && !node->right) {//到了叶子结点
        for (int i = index; i > 1; i--) {
            cout << arr[i] << "->";
        }
        cout << arr[1] << endl;
        if (index > maxlen) {//长度更长
            for (int i = 1; i <= index; i++) {
                maxpath[i] = arr[i];
            }
            maxlen = index;
        }
        return;
    }
    if (node->left) {
        preSearch(node->left, arr, index + 1, maxpath, maxlen);
    }
    if (node->right) {
        preSearch(node->right, arr, index + 1, maxpath, maxlen);
    }
}

void afterSearch(treenode* node) {
    treenode* arr[100];
    int index = -1;
    treenode* cur = node;
    treenode* pre = NULL;
    bool judge = false;
    do{
        while (cur) {
            index++;
            arr[index] = cur;
            cur = cur->left;
        }
        pre = NULL;
        judge = true;
        while (index > -1 && judge) {
            cur = arr[index];
            if (cur->right == pre) {
                if (cur->left == NULL && cur->right == NULL) {
                    for (int i = index; i > 0; i--) {
                        cout << arr[i]->data << "->";
                    }
                    cout << arr[0]->data << endl;
                }
                index--;
                pre = cur;
            }
            else {
                cur = cur->right;
                judge = false;
            }
        }
    } while (index > -1);
}
void lawyerSearch(treenode* root)
{
    struct newnode
    {
        treenode* node;
        int parent;
    }Qu[100];
    int front, rear, p;
    front = rear = -1;
    rear++;
    Qu[rear].node = root;
    Qu[rear].parent = -1;
    while (front < rear)
    {
        front++;
        root = Qu[front].node;
        if (root->left == NULL && root->right == NULL)
        {
            p = front;
            while (Qu[p].parent != -1)
            {
                cout << Qu[p].node->data << "->";
                p = Qu[p].parent;
            }
            printf("%c\n", Qu[p].node->data);
        }
        if (root->left != NULL)
        {
            rear++;
            Qu[rear].node = root->left;
            Qu[rear].parent = front;
        }
        if (root->right != NULL)
        {
            rear++;
            Qu[rear].node = root->right;
            Qu[rear].parent = front;
        }
    }
}
int main() {
    string tree = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
    treenode* root = new treenode;
    createtree(root, tree);//建树
    char arr[100];
    char maxpath[100];
    int maxlen = 0;
    cout << "前序遍历的路径为：" << endl;
    preSearch(root, arr, 1, maxpath, maxlen);

    cout << "最长的路径为：" << endl;
    for (int i = maxlen; i > 1; i--) {
        cout << maxpath[i] << "->";
    }
    cout << maxpath[1] << endl << endl;

    cout << "后序遍历的路径为：" << endl;
    afterSearch(root);
    cout << endl;

    cout << "层次遍历的路径为：" << endl;
    lawyerSearch(root);
    return 0;
}

